package day_03.second;

public class MaxHeap {
    private int[] data;
    private int count;
    private int capacity;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        data = new int[capacity + 1];
        count = 0;
    }

    public void insert(int value){
        assert count + 1 <= capacity;
        data[count + 1] = value;
        count++;
        shiftUp(count);
    }

    public int pop(){
        int ret = data[0];
        swap(data, 0, count);
        count--;
        shiftDown(count);
        return ret;
    }

    private void shiftDown(int k) {
        while(2 * k <= count){
            int j = 2 * k;
            if(j + 1 <= count && data[j + 1] > data[j]){
                j++;
            }
            if(data[k] > data[j]) break;
            swap(data, k, j);
            k = j;
        }
    }

    private void shiftUp(int k) {
        while (k + 1 < count && data[k] > data[k/2]){
            swap(data, k, k/2);
            k /= 2;
        }
    }

    private void swap(int[] data, int k, int i) {
        int tmp = data[k];
        data[k] = data[i];
        data[i] = tmp;
    }
}
